package leetcode.pre100;


/**
 * 假设按照升序排序的数组在预先未知的某个点上进行了旋转。
 * <p>
 * ( 例如，数组 [0,0,1,2,2,5,6] 可能变为 [2,5,6,0,0,1,2] )。
 * <p>
 * 编写一个函数来判断给定的目标值是否存在于数组中。若存在返回 true，否则返回 false。
 * <p>
 * 示例 1:
 * <p>
 * 输入: nums = [2,5,6,0,0,1,2], target = 0
 * 输出: true
 * 示例 2:
 * <p>
 * 输入: nums = [2,5,6,0,0,1,2], target = 3
 * 输出: false
 * <p>
 * 没有重复元素，
 * 见{@link leetcode.pre50.Code33_FindTargetInRotateArray}
 * <p>
 * 旋转数组其他问题
 * {@link leetcode.a_总结分布.Code13_旋转数组问题}
 */
public class Code81_FindTargetInRotateArray2 {
    public static void main(String[] args) {
        int[] nums = {9, 10, 11, 12, 13, 14, 15, 6, 7, 8};
        System.out.println(search(nums, 7));
    }

    /**
     * 第2类：数组非严格递增
     * 10111 和 11101 这种。
     * 此种情况下 nums[start] == nums[mid]，分不清到底是前面有序还是后面有序，
     * 此时 start++ 即可。相当于去掉一个重复的干扰项。
     */

    public static boolean search(int[] arr, int target) {
        if (arr == null || arr.length == 0) return false;
        int left = 0;
        int right = arr.length - 1;
        int mid = (left + right) / 2;
        //一直搜索，搜索一次判断target位于哪一侧
        while (left <= right) {
            if (arr[mid] == target) return true;
            //分不清10111 和 11101 哪种情况，去除一个重复值 ，因为该重复值肯定不是target
            if (arr[left] == arr[mid]) {
                left++;
                mid = (left + right) >> 1;
                continue;
            }
            //如果搜索来到左侧大的区域
            if (arr[left] <= arr[mid]) {
                //若target位于二者之间，顺序搜索
                if (arr[left] <= target && target <= arr[mid]) {
                    right = mid - 1;
                } else {//target位于mid+1后面
                    left = mid + 1;
                }
                //否则搜索来到右侧小的区域 ，arr[left] >  arr[mid]
            } else {
                //若target位于二者之间，顺序搜索
                if (arr[mid] <= target && target <= arr[right]) {
                    left = mid + 1;
                } else {//target位于mid-1后面
                    right = mid - 1;
                }
            }
            mid = (left + right) / 2;
        }
        return false;
    }

}
